package 数组;
import java.util.*;
/**
 * 该类用于查找两个有序数组的中位数。
 * 时间复杂度：O(n log n)，空间复杂度：O(n)
 */
public class findMedianSortedArrays {
    /**
     * 查找两个有序数组的中位数。
     * 该方法通过合并两个数组并排序，然后计算中位数。
     * @param nums1 第一个有序数组
     * @param nums2 第二个有序数组
     * @return 中位数
     */
    public double findMedian(int[] nums1, int[] nums2) {
        int[] arr = new int[nums1.length + nums2.length]; // 创建一个新数组，长度为两个输入数组长度之和
        int len = arr.length; // 获取新数组的长度
        for(int i = 0; i < len; i++) {
            if(i < nums1.length) arr[i] = nums1[i]; // 如果当前索引小于第一个数组的长度，复制第一个数组的元素
            else arr[i] = nums2[i - nums1.length]; // 否则，复制第二个数组的元素
        }
        // Arrays.sort(arr); // 使用Java内置排序
        quickSort(arr, 0, len - 1); // 使用快速排序对新数组进行排序
        double res; // 定义结果变量
        if(len % 2 != 0) res = arr[len / 2]; // 如果数组长度为奇数，中位数为中间元素
        else res = (arr[len / 2] + arr[len / 2 - 1]) * 0.5; // 如果数组长度为偶数，中位数为中间两个元素的平均值
        return res; // 返回中位数
    }

    /**
     * 快速排序算法。
     * 该方法通过递归的方式对数组进行排序。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right) {
        if(left >= right) return; // 如果左边界大于等于右边界，返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 递归排序左半部分
        quickSort(nums, pivot + 1, right); // 递归排序右半部分
    }

    /**
     * 分区函数，用于快速排序。
     * 该方法通过选择基准元素，将数组分为两部分。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的位置
     */
    private int partition(int[] nums, int left, int right) {
        int val = nums[left]; // 选择第一个元素作为基准
        while(left < right) {
            while(left < right && nums[right] >= val) right--; // 从右向左找小于基准的元素
            nums[left] = nums[right]; // 将小于基准的元素放到左边
            while(left < right && nums[left] <= val) left++; // 从左向右找大于基准的元素
            nums[right] = nums[left]; // 将大于基准的元素放到右边
        }
        nums[left] = val; // 将基准元素放到最终位置
        return left; // 返回基准元素的位置
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取两个数组，并输出它们的中位数。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s1 = sc.nextLine().split(","); // 读取第一个数组
        int[] nums1 = new int[s1.length]; // 创建第一个数组
        for(int i = 0; i < s1.length; i++) {
            nums1[i] = Integer.parseInt(s1[i]); // 解析第一个数组
        }
        String[] s2 = sc.nextLine().split(","); // 读取第二个数组
        int[] nums2 = new int[s2.length]; // 创建第二个数组
        for(int i = 0; i < s2.length; i++) {
            nums2[i] = Integer.parseInt(s2[i]); // 解析第二个数组
        }
        findMedianSortedArrays fmsa = new findMedianSortedArrays(); // 创建对象
        System.out.println(fmsa.findMedian(nums1, nums2)); // 输出中位数
        sc.close(); // 关闭扫描器
    }
}
